package binarysearch;


/**
 * 1. 两种分法
 *
 * int mid = (l + r + 1) >> 1    【l ~ mid -1】, 【mid, r】   因为 如 l = 2  r = 3  此时 mid = 2 无限循环
 * int mid = (l + r ) >> 1       【l ~ mid】, 【mid + 1, r】
 *  使用那种分界 看题目最终要什么
 *  本题要最小的错误版本  看l = r - 1时应该最终取l = 4 还是 r = 5
 *      mid 为true 可以不变
 *      本题 l = r -1 时 mid = l = 4  最终要l = r  停留在 r最小的错误版本处 因此因该 mid + 1 ~ r
 *      取第二种分界
 *
 * 2. mid = l + (r - l) >> 1  防止整数溢出
 */
public class 第一个错误的版本_278{
    // 找到 最小的true  true时 r= mid  false时  l = mid + 1   用 l ~ mid  mid + 1 ~ r   l = r时mid处刚好为true
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        while(l < r)  {
            // int mid = (l+r) >> 1;
            int mid = l + (r - l)/2; // 防止计算时溢出  l + r 刚好大于整数最大值的时候会有问题

            if(!isBadVersion(mid)) { // 遇到错误版本  l = mid + 1
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;

    }

    // 题目自己实现
    boolean isBadVersion(int version){return  false; }
}
